package com.julius.design.suanfa.tree;

/**
 * @author julius
 * @date 2021-10-27 上午 11:01
 * <p>
 *      输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 *      B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 *      https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
 * </p>
 */
public class IsSubTree {

    /**
     * 分析:
     *      B是A的子树的条件为:
     *          1. B的head存在于A中
     *          2. B的结构和数组存在于A中
     * @param A source
     * @param B target
     * @return B是否是A的子树
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null){
            return false;
        }
        boolean same = isSame(A, B);
        if(same){
            return true;
        }
        //比较根节点的左子树
        boolean left = isSubStructure(A.left, B);
        if(left){
            return true;
        }
        //比较根节点的右子树
        boolean right = isSubStructure(A.right,B);
        if(right){
            return true;
        }
        return false;
    }

    /**
     * 递归判断树结构是否相同，前序遍历
     * @param A
     * @param B
     * @return
     */
    public boolean isSame(TreeNode A,TreeNode B){
        if(B == null){
            //说明B已经遍历完了，并且都存在于A
            return true;
        }
        if(A == null){
            //说明A遍历完了，但是B还没有，说明A不包含B
            return false;
        }

        if(A.val != B.val){
            //A和B的值不相同
            return false;
        }
        //比较左子树
        boolean left = isSame(A.left, B.left);
        //比较右子树
        boolean right = isSame(A.right, B.right);

        return left && right;
    }
}
